『Copy-and-Patch Compilation: A fast compilation algorithm for high-level languages and bytecode』

1. どんなもの？

WebAssemblyへの高速コンパイル & パフォーマンスが良いコードを生成できることが示されている

2. 先行研究と比べてどこがすごい？

Copy-and-Patchで作られたWebAssemblyコンパイラは、Liftoffコンパイラより4.9倍から6.5倍高速にコードを生成できる

CoremarkとPolyBenchCというWebAssemblyベンチマークでは、生成されたコードはLiftoffコンパイラのものを39%〜63%上回る

3. 技術や手法のキモはどこ？

4. どうやって有効だと検証した？

WebAssemblyコンパイラはPolyBenchベンチマークによる起動までの時間と、起動から実行までの時間を散布図で比較

Fig. 6. Copy-and-Patch can be used by metaprogramming systems to speed up their interpreters past LLVM -O0. And it can be combined with LLVM to let the user request higher optimization levels when the increased performance can amortize the orders of magnitude higher compilation cost.

5. 議論はある？

6. 次に読むべき論文は？

Abstructionの訳

code:memo

高速なコンパイルは、最新のデータベースシステムのクエリコンパイラや、最新のブラウザのWebAssembly仮想マシンのように、実行時にコンパイルが行われる場合に重要である。我々は、非常に高速なコンパイル技術であり、かつ良質なコードを生成するコピー＆パッチを紹介する。コピー＆パッチは、バイナリ実装の大規模なライブラリからコードをつなぎ合わせることで、高レベル言語と低レベルバイトコードプログラムの両方をバイナリコードに変換することが可能です。これらのバイナリ実装は、コード生成時に欠損値を挿入しなければならない穴があるため、ステンシルと呼んでいます。ステンシルライブラリの構築方法を示し、最適化されたバイナリコードを生成するコピーアンドパッチアルゴリズムを説明する。

コピー＆パッチの使用例として、メタプログラミングを目的とした高レベルC言語用コンパイラとWebAssembly用コンパイラの2つを示す。このコンパイラは、ASTを構築するのにかかる時間よりも短い時間でASTからコードを生成することができ、コンパイルコストを無視できる。このメタプログラミングの上にSQLデータベースクエリーコンパイラを実装し、TPC-Hデータベースベンチマークにおいて、コピーアンドパッチはLLVM -O0よりも2桁、より高い最適化レベルよりも3桁高速にコードを生成することを示しました。また、生成されたコードは、解釈よりも1桁、LLVM -O0よりも14%高速に実行されます。WebAssemblyコンパイラは、Google ChromeのWebAssemblyベースラインコンパイラであるLiftoffよりも4.9倍から6.5倍高速にコードを生成します。また、CoremarkとPolyBenchCのWebAssemblyベンチマークでは、生成されたコードはLiftoffのものを39%〜63%上回っています。

Google ChromeのWebAssemblyベースラインコンパイラ

ベースラインコンパイラとは...?

CPUのベンチマーク

Transaction Processing Performance Council (TPC) によって定義されたデータベースのベンチマーク

多分著者の動画

Copy-and-Patch Compilation - YouTube

https://www.youtube.com/watch?v=PaQJcBdwG9Y

table:訳

startup delay 起動する

Pareto frontier パレートフロンティア

negligible 無視できる

empirically 経験的に

state-of-the-art 最先端の

domain-specific ドメイン固有の

envision 心に［思い］描く、想像する

notably 特に、とりわけ

type speculation 型推測？

関連